package dataStructure.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E> {
    protected TreeNode<E> root;

    /**
     * 创建新的节点
     */
    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode<>(e);
    }

    void preOrder() {
        System.out.println("先序遍历:");
        preOrder(root);
        System.out.println();
    }

    private void preOrder(TreeNode<E> root) {
        if (root == null) return;
        System.out.print(root.element + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    void inOrder() {
        System.out.println("中序遍历:");
        inOrder(root);
        System.out.println();
    }

    private void inOrder(TreeNode<E> root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.element + " ");
        inOrder(root.right);
    }

    void postOrder() {
        System.out.println("后序遍历:");
        postOrder(root);
        System.out.println();
    }

    private void postOrder(TreeNode<E> root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.element + " ");
    }

    private TreeNode<E> search(TreeNode<E> root, E target) {
        if (root == null) return null;
        if (root.element.equals(target))
            return root;
        TreeNode<E> resultL = search(root.left, target);
        if (resultL != null && resultL.element.equals(target)) return resultL;
        TreeNode<E> resultR = search(root.right, target);
        if (resultR != null && resultR.element.equals(target)) return resultR;
        return null;
    }

    public boolean insert(E target, E e, boolean isLeftChild) {
        // 如果之前是空二叉树 插入的元素就作为根节点
        if (root == null) {
            root = createNewNode(e);
        } else {
            TreeNode<E> searched = search(root, target);
            if (searched != null) {
                TreeNode<E> node = new TreeNode<>(e);
                node.parent = searched;
                if (isLeftChild) {
                    searched.left = node;
                } else {
                    searched.right = node;
                }
            } else {
                return false;
            }
        }
        return true;
    }

    public int leftChildCount(E target) {
        return leftChildCount(search(root, target));
    }

    private int leftChildCount(TreeNode<E> root) {
        if (root == null) {
            return 0;
        } else if (root.left != null) {
            return 1 + leftChildCount(root.left) + leftChildCount(root.right);
        } else {
            return leftChildCount(root.right);
        }
    }

    public int rightChildCount(E target) {
        return rightChildCount(search(root, target));
    }

    private int rightChildCount(TreeNode<E> root) {
        if (root == null) {
            return 0;
        } else if (root.right != null) {
            return 1 + rightChildCount(root.left) + rightChildCount(root.right);
        } else {
            return rightChildCount(root.left);
        }
    }

    private void addWeight(TreeNode<E> currentNode) {
        if (currentNode == null) {
            return;
        }
        currentNode.weight++;
        addWeight(currentNode.left);
        addWeight(currentNode.right);
    }

    /**
     * 二叉树层次遍历打印
     */
    public void printTree() {
        if (root == null) return;
        Queue<TreeNode<E>> queue = new LinkedList<>();
        int current = 1;//当前层 还未打印的结点个数
        int next = 0;//下一层结点个数
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode<E> currentNode = queue.poll();
            System.out.printf("%s", currentNode.element);
            if (currentNode.parent != null) {
                System.out.printf("(%s", currentNode.parent.element);
                if (currentNode.parent.left == currentNode) {
                    System.out.print(".L) ");
                } else {
                    System.out.print(".R) ");
                }
            } else {
                System.out.print("(root)");
            }
            current--;
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
                next++;
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
                next++;
            }

//            int maxCount = maxCount(currentNode);
//            for (int i = 0; i < maxCount; i++)
//                System.out.print("       ");
            if (current == 0) {
                System.out.println();
                current = next;
                next = 0;
            }
        }
    }

    public int maxCount(TreeNode<E> root) {
        int leftCount = leftChildCount(root);
        int rightCount = rightChildCount(root);
        int maxCount = Math.max(leftCount, rightCount);
        return maxCount;
    }
}
